package datastructure.book.tujiesuanfa.tree._2_more;

import datastructure.book.tujiesuanfa.tree.bean.Node;
import datastructure.book.tujiesuanfa.tree.bean.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Solution1 {

    /**
     * 第一层从左往右遍历，其余每层遍历顺序与上一层相反，每一层的结果放在一个list里
     * 第一层：从左往右、第二层：从右往左、第三层：从左往右
     */
    public List<List<Integer>> decorateRecord(TreeNode root) {
        if (root == null){
            return new ArrayList<>();
        }
        ArrayList<List<Integer>> lists = new ArrayList<>();
        ArrayList<TreeNode> treeNodes = new ArrayList<>();
        treeNodes.add(root);
        boolean flag = false;
        while (!treeNodes.isEmpty()){
            ArrayList<TreeNode> tempTreeNodes = new ArrayList<>();
            LinkedList<Integer> numList = new LinkedList<>();
            for (TreeNode treeNode : treeNodes) {
                if (flag){
                    numList.addFirst(treeNode.val);
                }else {
                    numList.addLast(treeNode.val);
                }
                if (treeNode.left != null){
                    tempTreeNodes.add(treeNode.left);
                }
                if (treeNode.right != null){
                    tempTreeNodes.add(treeNode.right);
                }
            }
            flag = !flag;
            lists.add(numList);
            treeNodes = tempTreeNodes;
        }
        return lists;
    }

    /**
     * 两棵二叉树 tree1 和 tree2，
     * 判断 tree2 是否以 tree1 的某个节点为根的子树具有 相同的结构和节点值
     * tree2为空返回false
     * tree1:
     *        [3]
     *    [6]     [7]
     * [1]  [8] []  []
     * tree2:
     *         [6]
     *       [1]  []
     * tree2 与 tree1 的一个子树拥有相同的结构和节点值。即 6 - > 1。
     */
    public boolean isSubStructure(TreeNode A, TreeNode B){
        if (A == null || B == null) {
            return false;
        }
        return isSubStructure0(A,B);
    }

    private boolean isSubStructure0(TreeNode a, TreeNode b) {
        if (a == null) {
            return false;
        }
        if (isSubStructure1(a, b)) {
            return true;
        }
        return isSubStructure0(a.left, b) || isSubStructure0(a.right, b);
    }

    private boolean isSubStructure1(TreeNode a, TreeNode b) {
        if (b == null) {
            return true;
        }
        if (a == null) {
            return false;
        }
        if (a.val == b.val) {
            return isSubStructure1(a.left,b.left)&& isSubStructure1(a.right,b.right);
        }
        return false;
    }

    /**
     * 将二叉搜索树转化为排序的双向链表
     * 将左右孩子指针作为双向循环链表的前驱和后继指针，
     * 第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点
     * 返回链表中最小元素的指针
     * Node.left.val < Node.val < Node.right.val
     *              4
     *      2               7
     *   1     3        6       8
     *               5
     *   [8]<=>1<=>2<=>3<=>4<=>5<=>6<=>7<=>8<=>[1]
     */
    private Node head = null;
    private Node pre = null;
    public Node treeToDoublyList(Node root) {
        if (root == null){
            return null;
        }
        treeToDoublyList0(root);
        pre.right = head;
        head.left = pre;
        return head;
    }

    public void treeToDoublyList0(Node root){
        if (root == null){
            return;
        }
        treeToDoublyList0(root.left);
        if (pre == null){
            head = root;
            pre = root;
        }else {
            pre.right = root;
            root.left = pre;
            pre = root;
        }
        treeToDoublyList0(root.right);
    }

    /**
     * 判断是否为平衡二叉树
     * 二叉树中任意节点的左右子树的深度相差不超过1那么它就是一棵平衡二叉树
     * 例：平衡二叉树
     *              10
     *        5            15
     *   2         7             20
     * 1        6     8
     * 非平衡二叉树
     *              10
     *        5            15
     *   2         7             20
     * 1        6     8
     *       3
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        boolean[] result = new boolean[]{true};
        isBalanced0(root,result);
        return result[0];
    }

    private int isBalanced0(TreeNode root,boolean[] result){
        if (root == null) {
            return 0;
        }
        if (!result[0]) {
            return 0;
        }
        int leftDepth = isBalanced0(root.left, result);
        if (!result[0]) {
            return 0;
        }
        int rightDepth = isBalanced0(root.right,result);
        if (!result[0]) {
            return 0;
        }
        if (Math.abs(leftDepth - rightDepth) > 1) {
            result[0] = false;
            return 0;
        }
        return Math.max(leftDepth,rightDepth)+1;
    }

    /**
     * 寻找二叉树的最近公共祖先
     * 例：3   8 最近公共祖先为 -1
     *           -1
     *       0         3
     *   -2    4
     * 8
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root.val == p.val || root.val == q.val) {
            return root;
        }
        TreeNode leftNode = lowestCommonAncestor(root.left, p, q);
        TreeNode rightNode = lowestCommonAncestor(root.right, p, q);
        if (leftNode != null && rightNode != null) {
            return root;
        }
        return leftNode == null ? rightNode : leftNode;
    }
}
